package algorithm;

import javafx.scene.layout.Priority;

import java.sql.Connection;
import java.util.*;

public class Practice {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<HashMap.Entry<String, Integer>> pq = new PriorityQueue<>(new Comparator<HashMap.Entry<String, Integer>>() {
            public int compare(HashMap.Entry<String, Integer> o1, HashMap.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0)
                    return o2.getKey().compareTo(o1.getKey());

                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (HashMap.Entry<String, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {  // 处理size < k时有特殊情况
                pq.offer(entry);
            } else {
                Map.Entry<String, Integer> e = pq.peek();
                if (e != null && e.getValue().compareTo(entry.getValue()) < 0) {
                    pq.poll();
                    pq.offer(entry);
                } else if (e != null && e.getValue().compareTo(entry.getValue()) == 0) {
                    if (e.getKey().compareTo(entry.getKey()) > 0) {
                        pq.poll();
                        pq.offer(entry);
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();

        while (!pq.isEmpty()) {
            Map.Entry<String, Integer> e = pq.poll();
            list.add(e.getKey());
        }

        Collections.reverse(list);

        return list;
    }
}
